package main.leetcode.clockin.July;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 315. 计算右侧小于当前元素的个数 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于
 * nums[i] 的元素的数量。
 *
 * <p>示例: 输入: [5,2,6,1] 输出: [2,1,1,0]<br>
 * 解释: 5 的右侧有 2 个更小的元素 (2 和 1). <br>
 * 2 的右侧仅有 1 个更小的元素 (1). <br>
 * 6 的右侧有 1 个更小的元素 (1). <br>
 * 1 的右侧有 0 个更小的元素.
 */
public class day11 {
    private int[] aux;
    private int[] index;
    private Integer[] res;

    // 暴力
    //    public List<Integer> countSmaller(int[] nums) {
    //        if (nums == null || nums.length == 0) {
    //            return new ArrayList<>();
    //        }
    //        int n = nums.length;
    //        Integer[] res = new Integer[n];
    //        Arrays.fill(res, 0);
    //        for (int i = n - 2; i >= 0; --i) {
    //            int cur = 0;
    //            for (int j = i + 1; j < n; ++j) {
    //                if (nums[i] > nums[j]) {
    //                    ++cur;
    //                }
    //            }
    //            res[i] = cur;
    //        }
    //        return Arrays.asList(res);
    //    }

    // 遍历 + 插排，勉强通过
    //    public List<Integer> countSmaller(int[] nums) {
    //        if (nums == null || nums.length == 0) {
    //            return new ArrayList<>();
    //        }
    //        int n = nums.length;
    //        Integer[] res = new Integer[n];
    //        int[] copy = nums.clone();
    //        res[n - 1] = 0;
    //        for (int i = n - 2; i >= 0; --i) {
    //            // 插排
    //            int j = i;
    //            for (; j < n - 1 && copy[j] <= copy[j + 1]; ++j) {
    //                copy[j] = copy[j] + copy[j + 1] - (copy[j + 1] = copy[j]);
    //            }
    //            res[i] = n - j - 1;
    //        }
    //        return Arrays.asList(res);
    //    }

    public static void main(String[] args) {
        System.out.println(new day11().countSmaller(new int[] {2, 0, 1, 1}));
        System.out.println(new day11().countSmaller(new int[] {2, 1, 1}));
    }

    // 归并排序
    public List<Integer> countSmaller(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }
        int n = nums.length;
        aux = new int[n];
        // 索引数组
        index = new int[n];
        res = new Integer[n];
        Arrays.fill(res, 0);
        for (int i = 0; i < n; ++i) {
            index[i] = i;
        }
        mergeSort(nums, 0, n - 1);
        return Arrays.asList(res);
    }

    private void mergeSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l >>> 1);
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        if (nums[index[mid]] <= nums[index[mid + 1]]) {
            return;
        }
        merge(nums, l, mid, r);
    }

    private void merge(int[] nums, int l, int mid, int r) {
        int i = l, j = mid + 1;
        System.arraycopy(index, l, aux, l, r - l + 1);
        for (int k = l; k <= r; ++k) {
            if (i > mid) {
                index[k] = aux[j++];
            } else if (j > r) {
                index[k] = aux[i++];
                res[index[k]] += j - mid - 1;
            } else if (nums[aux[i]] > nums[aux[j]]) {
                // j出列，这样写不对，并且实现麻烦
                //                res[aux[i]] += mid - i + 1;
                index[k] = aux[j++];
            } else {
                index[k] = aux[i++];
                res[index[k]] += j - mid - 1;
            }
        }
    }
}
